package vip.zhenzicheng.algorithm.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * <a href="https://leetcode.cn/problems/letter-combinations-of-a-phone-number/">电话号码的字母组合【中等】</a>
 *
 * @author zhenzicheng
 * @date 2022-12-22 17:52
 */
public class LetterCombinationsOfAPhoneNumber_17 {

  public List<String> letterCombinations(String digits) {
    List<String> combinations = new ArrayList<>();
    if (digits.length() == 0) {
      return combinations;
    }
    // 映射表
    Map<Character, String> phoneMap = new HashMap<>() {
      {
        put('2', "abc");
        put('3', "def");
        put('4', "ghi");
        put('5', "jkl");
        put('6', "mno");
        put('7', "pqrs");
        put('8', "tuv");
        put('9', "wxyz");
      }
    };
    backtrack(combinations, phoneMap, digits, 0, new StringBuilder());
    return combinations;
  }

  /**
   * 回溯
   *
   * @param
   * @param combinations 结果集
   * @param phoneMap     数字与字母映射关系表
   * @param src          原始入参，只包含数字的字符串
   * @param index        对原始字符串遍历指针，也控制递归的深度
   * @param buffer       遍历过程中拼接的结果字符串缓存
   */
  private void backtrack(List<String> combinations, Map<Character, String> phoneMap, String src, int index, StringBuilder buffer) {
    if (index == src.length()) {
      combinations.add(buffer.toString());
    } else {
      // 当前遍历到的字符
      char digit = src.charAt(index);
      String letters = phoneMap.get(digit);
      int count = letters.length();
      for (int i = 0; i < count; i++) {
        buffer.append(letters.charAt(i));
        // 继续递归处理当前节点下的子节点
        backtrack(combinations, phoneMap, src, index + 1, buffer);
        // 当前节点处理完，向上回溯
        buffer.deleteCharAt(index);
      }
    }
  }
}
